class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""

        dp = [[False] * len(s) for _ in range(len(s))]
        # 单字符肯定是回文
        for i in range(len(s)):
            dp[i][i] = True
            res = s[i]

        for i in range(len(s) - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                res = s[i : i + 2]
        print(dp)
        # 控制长度
        for n in range(3, len(s) + 1):
            # 控制多少个
            for i in range(len(s) - n + 1):
                print(s[i : i + n], i + 1, i + n - 2)
                if dp[i + 1][i + n - 2] and s[i] == s[i + n - 1]:
                    dp[i][i + n - 1] = True
                    res = s[i : i + n]
                else:
                    dp[i][i + n - 1] = False

        return res


if __name__ == "__main__":
    res = Solution().longestPalindrome("cbbd")
    print(res)

